/*
This file defines the class that contains edge related classes of the DDMCMC algorithm.
*/
#ifndef _DDMCMC_EDGES
#define _DDMCMC_EDGES

#include <opencv2\core\core.hpp>
#include <opencv2\imgproc\imgproc.hpp> 

using namespace cv;

#ifndef PI
#define	PI				3.1415926535897931
#endif

#define HUGE_PENALTY 10e10
#define SPL 0.25881904514 // sin(15 degree): pay 15 degrees per unit distance
#define MIN_CNT_STRENGTH -1E10
#define MAX_NBR_NUM 10

#define min(a, b)  (((a) < (b)) ? (a) : (b))
#define max(a, b)  (((a) > (b)) ? (a) : (b))

void printMatrix(Mat m, string fname);

class Contour;

class ContourNeighbor {
public:
	double	dContinuityStrength;
	int		nEnd;
	Contour *pContour;
	Point2i	point;

	ContourNeighbor() {
		dContinuityStrength = MIN_CNT_STRENGTH;
		nEnd = 0;
		pContour = NULL;
	}
};


class PointNode { // Details not hidden
public:
	Point2i	data;
	PointNode	*pNext;
	PointNode	*pPrev;
	PointNode()	{ 
		pNext = NULL; 
		pPrev = NULL; 
	}
};


class PointList { // Details not hidden
public:
	PointNode	*pHead;
	PointNode	*pTail;
	int			nSize;

	PointList() {
		pHead = NULL;
		pTail = NULL;
		nSize = 0;
	}

	Point2i getHeadOrTail(int endNo) {
		if (endNo == 0) return pHead->data;
		return pTail->data;
	}

	void addTail(Point2i p) {
		PointNode *newNode = new PointNode();
		if (pHead == NULL && pTail == NULL) {
			newNode->data = p;
			pHead = newNode;
			pTail = newNode;
		}
		else {
			PointNode *oldTail = pTail;
			oldTail->pNext = newNode;
			newNode->data = p;
			newNode->pPrev = oldTail;
			pTail = newNode;
		}
		nSize++;
	}

	void addHead(Point2i p) {
		PointNode *newNode = new PointNode();
		if (pHead == NULL && pTail == NULL) {
			newNode->data = p;
			pHead = newNode;
			pTail = newNode;
		}
		else {
			PointNode *oldHead = pHead;
			oldHead->pPrev = newNode;
			newNode->data = p;
			newNode->pNext = oldHead;
			pHead = newNode;
		}
		nSize++;
	}

	Point2i removeHead() {
		Point2i p(0, 0);
		if (pHead != NULL) {
			p = pHead->data;
			PointNode *pOldHead = pHead;
			pHead = pOldHead->pNext;
			delete pOldHead;
			if (pHead == NULL) pTail = NULL;
			else pHead->pPrev = NULL;
			nSize--;
		}
		return p;
	}
	
	Point2i removeTail() {
		Point2i p(0, 0);
		if (pTail != NULL) {
			p = pTail->data;
			PointNode *pOldTail = pTail;
			pTail = pOldTail->pPrev;
			delete pOldTail;
			if (pTail == NULL) pHead = NULL;
			else pTail->pNext = NULL;
			nSize--;
		}
		return p;
	}
};

class Contour {  // Details not hidden
public:
	Contour*		pNext;
	Contour*		pPrev;
	PointList		pointList;			// the list of points in the contour
	ContourNeighbor	aHeadNeighbor[MAX_NBR_NUM];	// the array of neighbors to the head point
	ContourNeighbor	aTailNeighbor[MAX_NBR_NUM];	// the array of neighbors to the tail point
	int				nHeadNeighbors;
	int				nTailNeighbors;
	int				nPoints;
	int				nLastMoveDir;		// the direction of last move, 0..8
	int				nHeadTailStatus[2]; //[0]head,[1]tail, -1 free, 0 reach itself,  1 reach other contour, 2 reach boundary
	double			dAngleHead;
	double			dAngleTail;
	bool			bExtendHeadTail[2];

	Contour() {
		pNext = NULL;
		pPrev = NULL;
		nPoints = 0;
		nLastMoveDir = 0;
		dAngleHead = 0;
		dAngleTail = 0;
		bExtendHeadTail[0] = true;
		bExtendHeadTail[1] = true;
		nHeadTailStatus[0] = -1;
		nHeadTailStatus[1] = -1;
		nHeadNeighbors = 0;
		nTailNeighbors = 0;
	}

	Contour(Point2i p1, Point2i p2) {
		Point2i p;

		pNext = NULL;
		pPrev = NULL;
		nPoints = 0;
		nLastMoveDir = 0;
		bExtendHeadTail[0] = true;
		bExtendHeadTail[1] = true;
		nHeadTailStatus[0] = -1;
		nHeadTailStatus[1] = -1;
		nHeadNeighbors = 0;
		nTailNeighbors = 0;
		
		if (abs(p2.x - p1.x) >= abs(p2.y - p1.y)) { // x as variable
			int nStep = getSign(p2.x - p1.x);
			if (nStep > 0) {
				for (int i = p1.x + 1; i <= p2.x - 1; i += nStep) {
					p.x = i;
					p.y = (int)(p1.y + (double)(i - p1.x) / (p2.x - p1.x)*(p2.y - p1.y));
					pointList.addTail(p);
				}
			}
			else if (nStep < 0) {
				for (int i = p1.x - 1; i >= p2.x + 1; i += nStep) {
					p.x = i;
					p.y = (int)(p1.y + (double)(i - p1.x) / (p2.x - p1.x)*(p2.y - p1.y));
					pointList.addTail(p);			
				}
			}
		}
		else { // y as variable
			int nStep = getSign(p2.y - p1.y);
			if(nStep > 0) {
				for (int i = p1.y + 1; i <= p2.y - 1; i += nStep) {
					p.y = i;
					p.x = (int)(p1.x + (double)(i - p1.y) / (p2.y - p1.y)*(p2.x - p1.x));
					pointList.addTail(p);
				}
			}
			else if (nStep < 0) {
				for (int i = p1.y - 1; i >= p2.y + 1; i += nStep) {
					p.y = i;
					p.x = (int)(p1.x + (double)(i - p1.y) / (p2.y - p1.y)*(p2.x - p1.x));
					pointList.addTail(p);
				}
			}
		}

		dAngleHead = (double)(atan2(p2.x - p1.x, p2.y - p1.y)); // the angle of the head point
		if (dAngleHead < 0) dAngleHead += PI;
		dAngleTail = dAngleHead - PI;
	}


	void addNeighbor(int endNo, ContourNeighbor cntNeighbor) {
		if (endNo == 0) {
			if (nHeadNeighbors < MAX_NBR_NUM) {
				aHeadNeighbor[nHeadNeighbors] = cntNeighbor;
				nHeadNeighbors++;
			}
		}
		else {
			if (nTailNeighbors < MAX_NBR_NUM) {
				aTailNeighbor[nTailNeighbors] = cntNeighbor;
				nTailNeighbors++;
			}
		}
	}

	int getNeighborNum(int endNo) {
		if (endNo == 0) return nHeadNeighbors;
		else return nTailNeighbors;
	}

	ContourNeighbor getNeighbor(int endNo, int i) {
		if (endNo == 0) return aHeadNeighbor[i];
		else return aTailNeighbor[i];
	}

	int getLengthFromPoint2End(int endNo, Point2i p) {
		int nLength = 0;
		PointNode *current;

		if (endNo == 0) {
			current = pointList.pHead;
			while (current != NULL) {
				nLength++;
				if (current->data == p)
					break;
				current = current->pNext;
			}
		}
		else {
			current = pointList.pTail;
			while (current != NULL) {
				nLength++;
				if (current->data == p)
					break;
				current = current->pPrev;
			}
		}
		return nLength;
	}

	void sortNeighbors(int endNo) {
		ContourNeighbor *pNbrArray;
		ContourNeighbor temp;
		double dSumStrength = 0;
		int nNeighbors;

		if (endNo == 0) {
			nNeighbors = nHeadNeighbors;
			pNbrArray = aHeadNeighbor;
		}
		else {
			nNeighbors = nTailNeighbors;
			pNbrArray = aTailNeighbor;
		}
		if (nNeighbors <= 0) return;

		for (int i = 0; i < nNeighbors; i++)
			dSumStrength += pNbrArray[i].dContinuityStrength;
		if (dSumStrength != 0) {
			for (int i = 0; i < nNeighbors; i++)
				pNbrArray[i].dContinuityStrength = (pNbrArray[i].dContinuityStrength / dSumStrength);
		}

		for (int i = 0; i < nNeighbors - 1; i++)
			for (int j = i + 1; j < nNeighbors; j++) {
				if (pNbrArray[i].dContinuityStrength < pNbrArray[j].dContinuityStrength) {
					temp = pNbrArray[i];
					pNbrArray[i] = pNbrArray[j];
					pNbrArray[j] = temp;
				}
			}
	}

	int getSign(int n) {
		if (n > 0) return 1;
		if (n == 0) return 0;
		return -1;
	}
};

class ContourList {
public:
	Contour *pHead;
	Contour *pTail;
	int		nSize;

	ContourList() {
		pHead = NULL;
		pTail = NULL;
		nSize = 0;
	}
	
	~ContourList() {
		Contour	*p = pHead;
		while (p != NULL) {
			Contour *pTemp = p->pNext;
			p->pNext = NULL;
			p->pPrev = NULL;
			delete p;
			p = pTemp;
		}
	}

	void addHead(Contour *pNew) {
		if (pHead == NULL && pTail == NULL) {
			pHead = pNew;
			pTail = pNew;
			pNew->pNext = NULL;
			pNew->pPrev = NULL;
		} else {
			Contour *pOldHead = pHead;
			pHead = pNew;
			pOldHead->pPrev = pHead;
			pHead->pNext = pOldHead;
			pHead->pPrev = NULL;
		}
		nSize++;
	}

	void addTail(Contour *pNew) {
		if (pHead == NULL && pTail == NULL) {
			pHead = pNew;
			pTail = pNew;
			pNew->pNext = NULL;
			pNew->pPrev = NULL;
		}
		else {
			Contour *pOldTail = pTail;
			pTail = pNew;
			pOldTail->pNext = pTail;
			pTail->pPrev = pOldTail;
			pTail->pNext = NULL;
		}
		nSize++;
	}

	// Memory not de-allocated
	void remove(Contour *p) {
		if (p == pHead) {
			pHead = pHead->pNext;
			pHead->pPrev = NULL;
		} else if (p == pTail) {
			pTail = pTail->pPrev;
			pTail->pNext = NULL;
		} else {
			Contour *p1 = p->pPrev;
			Contour* p2 = p->pNext;
			p1->pNext = p2;
			p2->pPrev = p1;
		}
		delete p;
	}
};

// Main class for edge-related processing
class DDMCMC_EdgePrcs {
public:
	DDMCMC_EdgePrcs(Mat mImage);
	~DDMCMC_EdgePrcs();

	int		getSign(int n);
	int		skeletonize(Mat &mEdges);
	int		getEdgeLocalMax();
	int		angle2Direction(double dAngle);
	int		traceContour4OverSegment(int endNo, Contour *pContour);
	void	segmentRegions(double dSigma, Mat &mRegionLabels);
	void	labelRegions(Mat &mRegionLabel);
	void	freeEndsOfAllContours();
	void	freeOneEndOfContour(Contour *pContour, Contour *pContourLinked, int endNo);
	void	getNeighborOfContour(Contour *pContour, int endNo);
	void	findNeighborMovingPts(Point2i p, int &n, Point2i &p1, Point2i &p2, Point2i &p3);
	void	buildContourList4OverSegment();
	void	getContourAtPoint4OverSegment(Point2i p, Contour *pNewContour);
	void	cutContour(Contour *pContour, Point2i p, int endNo);
	void	combineContour(Contour *pContour1, int endNo1, Contour* pContour2, int endNo2);
	void	setMatrixFlag(Mat m, PointList pointList, uchar value);
	void	setContourMatrix(Contour *pContour, bool bFlag);
	void	setParam(double dSigma);
	void	movePointIntoRegion(Point2i &p);
	void	labelRegionFromSeed(Mat &mRegionLabel, int x, int y, Point2i *pPoints);
	void	labelBoundaries(Mat &mRegionLabel);
	void	detectEdges();
	void	buildContours();

	double	direction2Angle(double dAngle, int nDir);
	double	calcPercentThreshold(Mat mImage, float dPercent, int nBins);
	double	calcAngle(Vec2d v);
	double	calcLength(Vec2d v);
	double	calcCompatibility(Vec2d v, Vec2d v1, Vec2d v2);
	double	calcContinuityStrength(Contour *pContour1, int &endNo1, Contour *pContour2, int &endNo2, Point2i p);
	bool	isNeighbor(Point2i p1, Point2i p2);
	bool	isLocalMax(int x, int y);
	bool	contourCrossSegLine(Contour &linkContour);
	Point2i	direction2Point(int nDir);
	Vec2d	direction2Vector(int nDir);

private:
	Mat			mRawImage, mEdges;
	Mat			Ix, Iy, mEdgeAngle, mEdgeStrength;
	Mat			mLocalMax;			// local max matrix
	Mat			mLocalMaxCJ;		// local max matrix for cross judge
	Mat			mLocalMaxFlag;
	Contour***	mContourMatrix;
	ContourList	contourList;

	double		dSigma;
	bool		bColor;
	int			cols;
	int			rows;
	int			nLabels;
	int			nMaxContourLength;
	int			nMinContourLength;
	int			mSearchDirection[9][9];
	Point2i		aPointNeighbor[8];

public:
};

#endif

